package com.leetcode.周赛.第232场;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author: xiaomi
 * @date: 2021/3/14
 * @description: 5703. 最大平均通过率
 * https://leetcode-cn.com/contest/weekly-contest-232/problems/maximum-average-pass-ratio/
 * https://leetcode-cn.com/problems/maximum-average-pass-ratio/
 * 没想到这么快就出题解了。
 */
public class B_5703_最大平均通过率 {

	static B_5703_最大平均通过率 action = new B_5703_最大平均通过率();

	public static void main(String[] args) {
		test1();
	}

	public static void test1() {
		int[][] classes = {{1, 2}, {3, 5}, {2, 2}};
		int extraStudents = 2;
		double res = action.maxAverageRatio(classes, extraStudents);
		System.out.println("res = " + res);
	}

	/**
	 * 假设加在值最小的上面
	 * 规律错误！
	 * --
	 * 看来想要解决本题，还需要有数学的基本知识才行：
	 * y+2/
	 * x+2
	 * −
	 * y+1/
	 * x+1
	 * <
	 * y+1/
	 * x+1
	 * −
	 * y/
	 * x
	 * 上面这个等式成立！
	 * 然后就是需要找到每一次班级通过率最小值，进行分子分母同时+1
	 *
	 * @param classes
	 * @param extraStudents
	 * @return
	 */
	public double maxAverageRatioFail(int[][] classes, int extraStudents) {
		int len = classes.length;
		Point[] tempArr = new Point[len];
		double tempRes = 0;
		PriorityQueue<Point> heap = new PriorityQueue<>(new Comparator<Point>() {
			@Override
			public int compare(Point o1, Point o2) {
				return o1.value - o2.value > 0 ? 1 : -1;
			}
		});
		for (int i = 0; i < len; i++) {
			double temp = classes[i][0] / (double) classes[i][1];
			tempRes += temp;
			Point point = new Point(classes[i][0], classes[i][1], temp);
			heap.add(point);
//            tempArr[i] = point;
		}
		Point cur = heap.remove();
		double t = (cur.son + extraStudents) / (double) (cur.mo + extraStudents);
		return (tempRes - cur.value + t) / len;

	}

	/**
	 * 似乎还是不能拿上面那个结论！
	 * heap 中应该存的是：下一次分子分母同时+1 后的增量
	 * 此时 heap 是个大根堆
	 * @param classes
	 * @param extraStudents
	 * @return
	 */
	public double maxAverageRatio(int[][] classes, int extraStudents) {
		int len = classes.length;
		double tempRes = 0;
		//需要一个大根堆，因为 diffValue 已经算出来了
		//说明接下来添加的就是 max diffValue
		PriorityQueue<Item> heap = new PriorityQueue<>(new Comparator<Item>() {
			@Override
			public int compare(Item o1, Item o2) {
				//return o1.diffValue - o2.diffValue > 0 ? 1 : -1;
				return o2.diffValue - o1.diffValue > 0 ? 1 : -1;
			}
		});
		for (int i = 0; i < len; i++) {
			if (classes[i][0] == classes[i][1]){
				tempRes++;
				continue;
			}
			double v = classes[i][0] / (double) classes[i][1];
			tempRes += v;
			double diff = ((classes[i][0] + 1) / (double) (classes[i][1] + 1)) - v;
			Item item = new Item(classes[i][0] + 1, classes[i][1] + 1, v, diff);
			heap.add(item);
		}
		if (heap.isEmpty()){
			//说明已经全部通过
			return 1;
		}
		//依次放入 多余的学生
		for (int i = 0; i < extraStudents; i++) {
			Item cur = heap.remove();
			tempRes += cur.diffValue;
			cur.value += cur.diffValue;
			cur.diffValue = (++cur.son) / (double) (++cur.mo) - cur.value;

			//再添加入堆
			heap.add(cur);
		}
		return tempRes / len;
	}

	static class Point {
		int son;
		int mo;
		double value;

		public Point(int son, int mo, double value) {
			this.son = son;
			this.mo = mo;
			this.value = value;
		}
	}

	static class Item {
		int son;
		int mo;
		double value;
		double diffValue;

		public Item(int son, int mo, double value, double diffValue) {
			this.son = son;
			this.mo = mo;
			this.value = value;
			this.diffValue = diffValue;
		}
	}
}
